#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* https://www.cnblogs.com/shuisanya/p/16873515.html */

#define MaxSize 100
#define MaxInteger 32767
//定义bool型常量
typedef enum {false, true} bool;

//边\弧
typedef struct ArcNode{
    //边或者弧指向的那个结点
    int adjvex;
    //指向下一个弧的指针
    struct ArcNode *next;
    //权值
    int info;
}ArcNode;

//顶点信息
typedef struct ElemType {
    //顶点信息
    char v;
    //顶点是否被使用，1表示使用，0表示未使用
    int flag;
}ElemType;

//顶点
typedef struct VNode {
    //顶点信息
    ElemType data;
    //第一个边或弧
    ArcNode *first;
}VNode, AdjList[MaxSize];

//有向图的邻接表存储
typedef struct MGraph {
    //图的信息
    AdjList vertices;
    //顶点数和边数
    int vexnum, arcnum;
}MGraph;

//初始化图
bool MG_Init(MGraph **G) {
    (*G) = (MGraph *)malloc(sizeof(MGraph));
    if(*G == NULL) {
        printf("申请内存失败! \n");
        return false;
    }
    //边数
    (*G)->arcnum = 0;
    //顶点数
    (*G)->vexnum = 0;
    //把所有待使用的顶点信息数据使用标志全置为0
    for(int i = 0; i < MaxSize; i++) {
        (*G)->vertices[i].data.flag = 0;
        (*G)->vertices[i].first = NULL;
    }
    return true;
}

//判断顶点V是否存在,并获取边的索引Vi
bool IsVEmpty(MGraph *G, ElemType V, int *Vi) {
    for(int i = 0; i < G->vexnum; i++) {
        if(G->vertices[i].data.v == V.v && G->vertices[i].data.flag == 1) {
            *Vi = i;
            return true;
        }
    }
    return false;
}

//判断边是否存在
bool Adjacent(MGraph *G, ElemType V, ElemType W, int *Vi, int *Wi) {
    if(!IsVEmpty(G, V, Vi) || !IsVEmpty(G, W, Wi)) {
        printf("其中一个顶点不存在！\n");
        return true;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while (node != NULL)
    {
        /* code */
        if(node->adjvex == *Wi) {
            // printf("边已经存在\n");
            return true;
        }
        node = node->next;
    }
    return false;
}

//插入顶点
bool InsertV(MGraph *G, ElemType V) {
    int *Vi;
    if(IsVEmpty(G, V, Vi)) {
        printf("顶点已经存在\n");
        return false;
    }
    V.flag = 1;
    G->vertices[G->vexnum++].data = V;
    return true;
}

//插入边
bool AddArcNode(MGraph *G, ElemType V, ElemType W, int info) {
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    //判断边是否存在
    if(Adjacent(G, V, W, Vi, Wi)) {
        return false;
    }
    ArcNode * p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = *Wi;
    p->info = info;
    p->next = NULL;
    //没有边，新增加边
    if(G->vertices[*Vi].first == NULL) {
        G->vertices[*Vi].first = p;
        G->arcnum++;
        return true;
    }
    //有边，末尾增加边
    ArcNode *node = G->vertices[*Vi].first;
    while (node->next != NULL)
    {
        /* code */
        node = node->next;
    }
    node->next = p;
    G->arcnum++;
    return true;
}

//获取某个结点v的所有邻接边;<v,wi>;以v为尾巴
bool NeighBors(MGraph *G, ElemType V, ElemType ***res, int **infos, int *length) {
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G, V, Vi)) {
        return false;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while (node != NULL)
    {
        /* code */
        (*length)++;
        node = node->next;
    }
    *res = (ElemType *)malloc(sizeof(ElemType) * (*length));
    *infos = (int *)malloc(sizeof(int) * (*length));
    node = G->vertices[*Vi].first;
    for(int i = 0; i < (*length); i++) {
        (*res)[i] = (ElemType *)malloc(sizeof(ElemType) * 3);
        (*res)[i][0] = V;
        (*res)[i][1] = G->vertices[node->adjvex].data;
        (*infos)[i] = node->info;
        node = node->next;
    }
    return true;
}

//移除该边<V,W>
bool RemoveArcNode(MGraph *G, ElemType V, ElemType W) {
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    //判断该边是否存在
    if(!Adjacent(G, V, W, Vi, Wi)) {
        return false;
    }
    //删除的结点
    ArcNode *delete = G->vertices[*Vi].first;
    //删除边的前一个结点
    ArcNode *pre = NULL;
    //寻找删除的边
    while (delete != NULL)
    {
        /* code */
        if(delete->adjvex == *Wi) {
            break;
        }
        pre = delete;
        delete = delete->next;
    }
    if(pre == NULL) {
        G->vertices[*Vi].first = G->vertices[*Vi].first->next;
    } else {
        //修改指针
        pre->next = delete->next;
    }
    //修改边数
    G->arcnum--;
    //释放内存
    free(delete);

    return true;
}

//删除顶点
bool DeleteV(MGraph *G, ElemType V) {
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G, V, Vi)) {
        return false;
    }
    ArcNode *W = G->vertices[*Vi].first;
    while (W != NULL)
    {
        /* code */
        RemoveArcNode(G, V, G->vertices[G->vertices[*Vi].first->adjvex].data);
        W = G->vertices[*Vi].first;
    }
    int index = 0;
    int sum = 0;
    while (sum < G->vexnum)
    {
        /* code */
        if(G->vertices[index].data.flag == 1) {
            W = G->vertices[index].first;
            while (W != NULL)
            {
                /* code */
                if(W->adjvex == *Vi) {
                    RemoveArcNode(G, G->vertices[index].data, V);
                    break;
                }
                W = W->next;
            }
            sum++;
        }
        index++;
    }
    G->vertices[*Vi].data.flag = 0;
    G->vexnum--;
    return true;
}

//队列的数据信息
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
}LinkNode;

//链队列定义
typedef struct {
    //*front 队头指针, *rear 队尾指针
    LinkNode *front, *rear;
}LinkQueue;

//初始化带头结点的队列
bool InitLinkQueue(LinkQueue *Q) {
    (*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkQueue));
    if((*Q).front == NULL || (*Q).rear == NULL) {
        return false;
    }
    (*Q).front->next = NULL;
    return true;
}

//带头结点判断是否为空
bool IsEmpty(LinkQueue Q) {
    if(Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

//带头结点入队操作
bool EnQueue(LinkQueue *Q, int e) {
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    //分配内存失败
    if(p == NULL) {
        return false;
    }
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return true;
}

//带头结点出队操作
bool DeQueue(LinkQueue *Q, int *e) {
    //队列为空，出队失败
    if(Q->front == Q->rear) {
        return false;
    }
    LinkNode *p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    //如果出队的元素是对尾元素，需要特殊处理
    if(Q->rear == p) {
        Q->rear = Q->front;
    }
    //释放
    free(p);
    return true;
}

//拓扑排序  图G,print:表示结果集
bool TopologicalSort(MGraph *G, char **print) {
    //入度记录的数组
    int *visited = (int *)malloc(sizeof(int) * G->vexnum);
    //返回的拓扑排序序列
    *print = (char *)malloc(sizeof(char) * G->vexnum);
    //初始化入度记录数组和拓扑排序结果集
    for(int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;
        (*print)[i] = '~';
    }
    //根据图G更新入度记录的数组
    for(int i = 0; i < G->vexnum; i++) {
        ArcNode *node = G->vertices[i].first;
        while (node != NULL)
        {
            /* code */
            visited[node->adjvex]++;
            node = node->next;
        }
    }
    //定义队列
    LinkQueue Q;
    //初始化队列
    InitLinkQueue(&Q);
    //入队列的顶点数目
    int count = 0;
    //入度为0的入队列
    for(int i = 0; i < G->vexnum; i++) {
        if(visited[i] == 0) {
            EnQueue(&Q, i);
        }
    }
    //循环队列是否为空，寻找其他顶点
    while (!IsEmpty(Q))
    {
        /* code */
        //队列的队头元素
        int e;
        //获取队列队头元素
        DeQueue(&Q, &e);
        //获取队头元素的值记入结果集
        (*print)[count++] = G->vertices[e].data.v;
        ArcNode *node = G->vertices[e].first;
        //寻找队头元素该顶点的边
        while (node != NULL)
        {
            /* code */
            //入度--，如果为0了就加入队列
            if(--visited[node->adjvex] == 0) {
                EnQueue(&Q, node->adjvex);
            }  
            node = node->next;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
        }
    }
    //全部进入队列返回拓扑排序成功，否则返回失败
    if(count = G->vexnum) {
        return true;
    } else {
        return false;
    }
}

//打印拓扑排序的结果集合
void printTopo(MGraph *G, char *print) {
    printf("拓扑排序的结果： ");
    for(int i = 0; i < G->vexnum; i++) {
        printf("%2c", print[i]);
    }
}

//拓扑排序使用
void TopoSort(MGraph *G) {
    char *print;
    bool flag = TopologicalSort(G, &print);
    if(flag) {
        printTopo(G, print);
    } else {
        printf("不是AOV网，拓扑排序失败");
    }
}

//构造有向网
void CreateUDG(MGraph *G) {
    ElemType V1;
    V1.v = 'A';
    InsertV(G, V1);
    ElemType V2;
    V2.v = 'B';
    InsertV(G, V2);
    ElemType V3;
    V3.v = 'C';
    InsertV(G,V3);
    ElemType V4;
    V4.v = 'D';
    InsertV(G,V4);
    ElemType V5;
    V5.v = 'E';
    InsertV(G,V5);
    ElemType V6;
    V6.v = 'F';
    InsertV(G,V6);
    ElemType V7;
    V7.v = 'G';
    InsertV(G,V7);
    AddArcNode(G,V1,V2,1);
    AddArcNode(G,V1,V6,1);
    AddArcNode(G,V2,V3,1);
    AddArcNode(G,V3,V7,1);
    AddArcNode(G,V4,V2,1);
    AddArcNode(G,V4,V5,1);
    AddArcNode(G,V5,V6,1);
    AddArcNode(G,V6,V3,1);
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    MGraph *G;
    MG_Init(&G);
    printf("顶点数：%d; 边数：%d\n", G->vexnum, G->arcnum);
    CreateUDG(G);
    printf("顶点数：%d; 边数：%d\n", G->vexnum, G->arcnum);
    TopoSort(G);
    return 0;
}